package com.waiseongou.leetcode_practice;

import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Processer {

    public static void main(String[] args) {
////        String roman = "a ";
////        System.out.println(lengthOfLastWord(roman));
//        String testText = " ";
//        String s = "aacc";
//        String t = "ccac";
//        String[] strs = {"flower","flow","flight"};
//        Integer[] intArray = { 2, 3, 4, 2, 6, 5 };
////        String regex = "\\w";
////        takeStringMatchRegex(regex, testText);
//        System.out.println(isAnagram(s, t));

//        String strS = "cabcac";
//        int pairList[][] = new int [3][2];
//        pairList[0][0] = 1;
//        pairList[0][1] = 6;
//        pairList[1][0] = 1;
//        pairList[1][1] = 3;
//        pairList[2][0] = 2;
//        pairList[2][1] = 5;
////        System.out.println(pairList.length); //3
////        System.out.println(pairList[0].length); //2
//        System.out.println(mostFrequent(strS, pairList));
//        Character a = 'a';
//        Character b = 'b';
//        System.out.println(a.compareTo(b));

        String parent = "tim";
        String sub = "tim";
        System.out.println(countOccur(parent, sub));
    }

    //80. 删除有序数组中的重复项 II
//    public int removeDuplicates2(int[] nums) {
//    }

    //26. 删除有序数组中的重复项
    public int removeDuplicates(int[] nums) {
        Set<Integer> appeared = new HashSet<>();
        int indexSlow = 0;
        for (int indexFast = 0; indexFast < nums.length; indexFast++) {
            if (!appeared.contains(nums[indexFast])) {
                nums[indexSlow] = nums[indexFast];
                indexSlow++;
                appeared.add(nums[indexFast]);
            }
        }
        return indexSlow;
    }

    //27. 移除元素
    public static int removeElement(int[] nums, int val) {
        int result = 0;
        int indexSlow = 0;
        for (int indexFast = 0; indexFast < nums.length; indexFast++) {
            if (nums[indexFast] != val) {
                nums[indexSlow] = nums[indexFast];
                result++;
                indexSlow++;
            }
        }
        return result;
    }

    //countOccur
    public static int countOccur(String parent, String sub) {
        int result = 0;
        if (sub.length() > parent.length()){
            return result;
        }
        parent = parent.toLowerCase();
        sub = sub.toLowerCase();
        int index = parent.indexOf(sub);
        while (index >= 0) {
            result++;
            parent = parent.substring(index+sub.length());
            index = parent.indexOf(sub);
        }
        return result;
    }

    public static int countOccur3(String parent, String sub) {
        int result = 0;
        if (sub.length() > parent.length()){
            return result;
        }
        char[] parentArray = parent.toLowerCase().toCharArray();
        char[] subArray = sub.toLowerCase().toCharArray();
        int parentIndex = 0;
        int subIndex = 0;
        boolean matching = false;
        while (parentIndex < parentArray.length) {
            if (parentArray[parentIndex] == subArray[subIndex]) {
                matching = true;
                subIndex++;
                if (subIndex == subArray.length) {
                    matching = false;
                    result += 1;
                    subIndex = 0;
                }
            } else {
                if (matching) {
                    subIndex = 0;
                    matching = false;
                    if (parentArray[parentIndex] == subArray[subIndex]) {
                        matching = true;
                        subIndex++;
                    }
                }
            }
            parentIndex++;
        }
        return result;
    }
    public static int countOccur2(String parent, String sub) {
        if (sub.length() > parent.length()){
            return 0;
        }
        Pattern pattern = Pattern.compile(sub.toLowerCase());
        Matcher matcher = pattern.matcher(parent.toLowerCase());
        int result = 0;
        while (matcher.find()) {
            result = result + 1;
        }
        return result;
    }

    // mostFrequent
    public static String mostFrequent(String strS, int[][] pairList) {
        StringBuffer result = new StringBuffer();
        for (int i = 0; i < pairList.length; i++) {
            Map<Character, Integer> map = new HashMap();
            for (int j = pairList[i][0]-1; j < strS.length() && j < pairList[i][1]; j++) {
                map.put(strS.charAt(j), map.getOrDefault(strS.charAt(j), 0) + 1);
            }

//            List<Character> list = new ArrayList<>(map.keySet());
            List<Character> list = new ArrayList<>();
            for (Map.Entry<Character, Integer> entry : map.entrySet()) {
                list.add(entry.getKey());
            }
//            list.sort((a, b) -> map.get(b) - map.get(a));
            list.sort((a, b) -> {
                if (map.get(b) - map.get(a) != 0) {
                    return map.get(b) - map.get(a);
                } else {
                    return a.compareTo(b);
                }
            });
            result.append(list.get(0));
        }
        return result.toString();
    }

    //242. 有效的字母异位词
    public static boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        Map<Character, Integer> sMap = new HashMap<>();
        for (Character c : s.toCharArray()) {
            sMap.put(c, sMap.getOrDefault(c,0) + 1);
        }
        for (Character c : t.toCharArray()) {
            int temp = sMap.getOrDefault(c, 0) - 1;
            if (temp < 0) {
                return false;
            } else {
                sMap.put(c, temp);
            }
        }
        return true;
    }
    //2 3 4 2 -> 0 3 3 3 -> 2 3 4
    //2 4 2 3 -> 0 3 3 3 -> 2 3 4
    //2 4 2 1 -> 3 3 0 3 -> 1 2 4
    //3 4 5 2 1 7 6 -> 3 2 3 2 3 2 2 -> 1 3 5
    //2 3 4 2 6 5 -> 0 3 3 3 2 2 -> 2 3 4
    public static List<Integer> maxAlumni(Integer[] allAlumni) {
        Map<Integer, Integer> calculatedMap = new HashMap<>();
        List<Integer> numberOfAttendeeIfXIdAttend = new ArrayList<>();
        List<Integer> result = new ArrayList<>();
        int maxNumber = 0;
        for (int id = 1; id <= allAlumni.length; id++) {
            Set<Integer> tempSet = new HashSet<>();
            if (!calculatedMap.keySet().contains(id)) {
                int number = findNumberOfAttendeeIfXIdAttend(allAlumni, id, id, tempSet);
                numberOfAttendeeIfXIdAttend.add(number);
                if (number!=0) {
                    if (maxNumber < number) {
                        maxNumber = number;
                    }
                    tempSet.forEach(key -> {
                        calculatedMap.put(key, number);
                    });
                }
            } else {
                numberOfAttendeeIfXIdAttend.add(calculatedMap.get(id));
            }
        }
        System.out.println(numberOfAttendeeIfXIdAttend);
        for (int i = 1; i <= numberOfAttendeeIfXIdAttend.size(); i++) {
            if (numberOfAttendeeIfXIdAttend.get(i-1) == maxNumber) {
                result.add(i);
            }
        }
        return result;
    }

    public static Integer findNumberOfAttendeeIfXIdAttend(Integer[] allAlumni, int originalId, int idCalculate, Set<Integer> tempSet) {
        tempSet.add(idCalculate);
        int thisIdLike = allAlumni[idCalculate-1];
        if (!tempSet.contains(thisIdLike)) {
            tempSet.add(thisIdLike);
            return findNumberOfAttendeeIfXIdAttend(allAlumni, originalId, thisIdLike, tempSet);
        } else {
            if (thisIdLike == originalId) {
                return tempSet.size();
            } else {
                return 0;
            }
        }
    }

    //最多连续工作周数
    public static Integer maxWorkingWeeks(Integer[] integers) {
        List<Integer> list = new ArrayList(Arrays.asList(integers));
        list.sort((a, b) -> b - a);
        int sumExcludeMax = 0;
        for (int i = 1; i < list.size(); i++) {
            sumExcludeMax += list.get(i);
        }
        if (list.get(0) > sumExcludeMax) {
            return sumExcludeMax * 2 + 1;
        } else {
            return list.get(0) + sumExcludeMax;
        }
    }
    //a,b,e,d,c
    //2,3,5,6,4
    //451. 根据字符出现频率排序
    public static String frequencySort(String s) {
        Map<Character, Integer> map = new HashMap<>();
        StringBuffer result = new StringBuffer();
        for (int i = 0; i < s.length(); i++) {
            s.charAt(i);
            map.put(s.charAt(i), map.getOrDefault(s.charAt(i),0)+1);
        }
        List<Character> list = new ArrayList<>(map.keySet());
        list.sort((a, b) -> map.get(b) - map.get(a));
        list.forEach(key -> {
            for (int i = 0; i < map.get(key); i++) {
                result.append(key);
            }
        });
        return result.toString();
    }
//    //135. 分发糖果
//    /*
//        ratings = {1 2 2 3 3 2 1}
//        candys  = {1 2 1 2 3 2 1}
//     */
//    public int candy(int[] ratings) {
//
//    }

    //290. 单词规律 (双射)
    public static boolean wordPattern(String s, String t) {
        if (!(s.length() == t.split(" ").length)) {
            return false;
        }
        Map<Character, String> map = new HashMap<>();
        Map<String, Character> map2 = new HashMap<>();
        char[] sArray = s.toCharArray();
        String[] tArray = t.split(" ");
        int index = 0;
        while (index < sArray.length) {
            if (map.get(sArray[index]) == null && map2.get(tArray[index]) == null) {
                map.put(sArray[index], tArray[index]);
                map2.put(tArray[index], sArray[index]);
            } else if (!(map.get(sArray[index]) == null) && !(map2.get(tArray[index]) == null)) {
                if (!(map.get(sArray[index]).equals(tArray[index]))) {
                    return false;
                }
            } else {
                return false;
            }
            index++;
        }
        return true;
    }

    //205. 同构字符串(检查双射)
    public static boolean isIsomorphic(String s, String t) {
        if (!(s.length() == t.length())) {
            return false;
        }
        Map<Character, Character> map = new HashMap<>();
        Map<Character, Character> map2 = new HashMap<>();
        char[] sArray = s.toCharArray();
        char[] tArray = t.toCharArray();
        int index = 0;
        while (index < sArray.length) {
            if (map.get(sArray[index]) == null && map2.get(tArray[index]) == null) {
                map.put(sArray[index], tArray[index]);
                map2.put(tArray[index], sArray[index]);
            } else if (!(map.get(sArray[index]) == null) && !(map2.get(tArray[index]) == null)) {
                if (!(map.get(sArray[index])==tArray[index])) {
                    return false;
                }
            } else {
                return false;
            }
            index++;
        }
        return true;
    }
    //383. 赎金信
    public boolean canConstruct(String ransomNote, String magazine) {
        if (ransomNote.length() > magazine.length()) {
            return false;
        }
        Map<Character, Integer> magazineLetterMap = new HashMap<>();
        for (char letter : magazine.toCharArray()) {
            magazineLetterMap.put(letter, magazineLetterMap.getOrDefault(letter, 0) + 1);
        }
        for (char letter : ransomNote.toCharArray()) {
            if (magazineLetterMap.getOrDefault(letter, 0) == 0) {
                return false;
            } else {
                magazineLetterMap.put(letter, magazineLetterMap.get(letter) - 1);
            }
        }
        return true;
    }
    public boolean canConstruct2(String ransomNote, String magazine) {
        if (magazine.length() < ransomNote.length()) {
            return false;
        }
        Map<Character, Integer> ransomNoteLetterMap = new HashMap<>();
        Map<Character, Integer> magazineLetterMap = new HashMap<>();
        char[] ransomNoteLetterArray = ransomNote.toCharArray();
        char[] magazineLetterArray = magazine.toCharArray();
        int ransomNoteIndex = 0;
        int magazineIndex = 0;
        while (ransomNoteIndex < ransomNoteLetterArray.length) {
            if (ransomNoteLetterMap.get(ransomNoteLetterArray[ransomNoteIndex]) == null) {
                ransomNoteLetterMap.put(ransomNoteLetterArray[ransomNoteIndex], 1);
            } else {
                ransomNoteLetterMap.put(ransomNoteLetterArray[ransomNoteIndex], ransomNoteLetterMap.get(ransomNoteLetterArray[ransomNoteIndex]));
            }
            ransomNoteIndex++;
        }
        while (magazineIndex < magazineLetterArray.length) {
            if (magazineLetterMap.get(magazineLetterArray[magazineIndex]) == null) {
                magazineLetterMap.put(magazineLetterArray[magazineIndex], 1);
            } else {
                magazineLetterMap.put(magazineLetterArray[magazineIndex], magazineLetterMap.get(magazineLetterArray[magazineIndex]));
            }
            magazineIndex++;
        }
        Set<Character> ransomKeySet = ransomNoteLetterMap.keySet();
        if (!magazineLetterMap.keySet().containsAll(ransomKeySet)) {
            return false;
        }
        while (ransomKeySet.iterator().hasNext()) {
            char key = ransomKeySet.iterator().next();
            if (magazineLetterMap.get(key) != null && ransomNoteLetterMap.get(key) > magazineLetterMap.get(key)) {
                return false;
            }
        }
        return true;
    }

    //392. 判断子序列（双指针）
    public static boolean isSubsequence(String s, String t) {
        char[] sArray = s.toCharArray();
        char[] tArray = t.toCharArray();
        int indexT = 0;
        int indexS = 0;
        while (indexS < sArray.length && indexT < tArray.length) {
            if (sArray[indexS] == tArray[indexT]) {
                indexT++;
                indexS++;
            } else {
                indexT++;
            }
        }
        if (indexS==sArray.length) {
            return true;
        } else {
            return false;
        }
    }

    public static String takeStringMatchRegex(String regex, String originalString) {
        Pattern pattern = Pattern.compile(regex);
        Matcher matcher = pattern.matcher(originalString);

        while (matcher.find()) {
            System.out.println(matcher.group());
        }
        return null;
    }

    //125. 验证回文串（双指针）
    public static boolean isPalindrome(String s) {
        if (s.length()<2) {
            return true;
        }
        String stringMid = s.toLowerCase();
        Pattern pattern = Pattern.compile("[a-z]");
        Matcher matcher = pattern.matcher(stringMid);
        List<String> stringAfter = new ArrayList<>();
        while (matcher.find()) {
            stringAfter.add(matcher.group());
        }
        if (stringAfter.size()<2) {
            return true;
        }
        for (int i = 0; i < stringAfter.size()/2; i++) {
            if (!stringAfter.get(i).equals(stringAfter.get(stringAfter.size()-1-i))) {
                return false;
            }
        }
        return true;
    }
    public static boolean isPalindromeLeetCode(String s) {
        StringBuffer sgood = new StringBuffer();
        int length = s.length();
        for (int i = 0; i < length; i++) {
            char ch = s.charAt(i);
            if (Character.isLetterOrDigit(ch)) {
                sgood.append(Character.toLowerCase(ch));
            }
        }
        int n = sgood.length();
        int left = 0, right = n - 1;
        while (left < right) {
            if (Character.toLowerCase(sgood.charAt(left)) != Character.toLowerCase(sgood.charAt(right))) {
                return false;
            }
            ++left;
            --right;
        }
        return true;
    }

    //14. 最长公共前缀 (复杂度O(mn)双循环是最佳)
    public static String longestCommonPrefix(String[] strs) {
        int index = 0;
        boolean endAlgo = false;
        StringBuilder commonPrefix = new StringBuilder();
        while (index < strs[0].length()) {
            for (int loopStrsIndex = 1; loopStrsIndex < strs.length; loopStrsIndex++) {
                if (index == strs[loopStrsIndex].length() || !(strs[0].charAt(index) == strs[loopStrsIndex].charAt(index))) {
                    endAlgo = true;
                    break;
                }
            }
            if (endAlgo) {
                return commonPrefix.toString();
            }
            commonPrefix.append(strs[0].charAt(index));
            index++;
        }
        return commonPrefix.toString();
    }

    //58. 最后一个单词的长度
    public static int lengthOfLastWord(String s) {
        String[] words = s.split(" ");
        int i = words.length - 1;
        if (0 == i) {
            return s.trim().length();
        }
        int lengthOfLastWord = 0;
        while (i > 0) {
            if (words[i].isEmpty()) {
                i--;
            } else {
                lengthOfLastWord = words[i].length();
                break;
            }
        }
        return lengthOfLastWord;
    }

    //13. 罗马数字转整数
    public static int romanToInt(String s) {
        int i = 0;
        int sum = 0;
        while (i < s.length()) {
            if (i == s.length()-1) {
                sum += romanToIntSimple(s.substring(s.length()-1));
                i++;
            } else {
                String temp = s.substring(i, i+2);
                if (temp.equals("IV") || temp.equals("IX") || temp.equals("XL") || temp.equals("XC") || temp.equals("CD") || temp.equals("CM")) {
                    sum += romanToIntSimple(s.substring(i, i+2));
                    i += 2;
                } else {
                    sum += romanToIntSimple(s.substring(i, i+1));
                    i++;
                }
            }
        }
        return sum;
    }
    public static int romanToIntSimple(String s) {
        return switch (s) {
            case "I" -> 1;
            case "V" -> 5;
            case "X" -> 10;
            case "L" -> 50;
            case "C" -> 100;
            case "D" -> 500;
            case "M" -> 1000;
            case "IV" -> 4;
            case "IX" -> 9;
            case "XL" -> 40;
            case "XC" -> 90;
            case "CD" -> 400;
            case "CM" -> 900;
            default -> 0;
        };
    }

    //55. 跳跃游戏
    public static boolean canJump(int[] nums) {
        int index = 0;
        int maxPosition = 0;
        while (index < nums.length) {
            int currentMaxPosition = index + nums[index];
            if (currentMaxPosition >= nums.length - 1) {
                return true;
            } else {
                if (currentMaxPosition > maxPosition) {
                    maxPosition = currentMaxPosition;
                } else {
                    if (nums[index] == 0 && index == maxPosition) {
                        return false;
                    }
                }
            }
            index++;
        }
        return maxPosition >= nums.length;
    }
}
